package sit.engreal.leetcode.mianshi;

import org.junit.jupiter.api.Assertions;

import java.util.TreeSet;

/**
 * <a href="https://leetcode.cn/problems/get-kth-magic-number-lcci/">面试题 17.09. 第 k 个数</a>
 */
public class T17T09 {
    public int getKthMagicNumber(int k) {
        final TreeSet<Integer> tree = new TreeSet<>();
        tree.add(1);
        int v = 1;
        for (int i = 0; i < k; i++) {
            v = tree.pollFirst();
            if ((v * 3) / 3 == v) {
                tree.add(v * 3);
            }
            if ((v * 5) / 5 == v) {
                tree.add(v * 5);
            }
            if ((v * 7) / 7 == v) {
                tree.add(v * 7);
            }
        }
        return v;
    }

    public static void main(String[] args) {

        final T17T09 demo = new T17T09();
        Assertions.assertEquals(9, demo.getKthMagicNumber(5));
        Assertions.assertEquals(1937102445, demo.getKthMagicNumber(643));
    }
}
